/*
 * Copyright 2002-2004 the original author or authors.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *      http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

using System;
using System.Collections;

namespace Spring.Collections
{
	/// <summary>
	/// Simple linked list implementation.
	/// </summary>
	/// <author>Simon White</author>
	public class LinkedList : IList
	{
		private int _nodeIndex;
		private Node _rootNode;
		private int _modId;

		#region Constructors
		/// <summary>
		/// Constructs a new <code>LinkedList</code>.
		/// </summary>
		public LinkedList()
		{
			_rootNode = new Node(null, null, null);
			_rootNode.PreviousNode = _rootNode;
			_rootNode.NextNode = _rootNode;
			_nodeIndex = 0;
		}

		/// <summary>
		/// Constructs a new <code>LinkedList</code> that contains all elements
		/// of the specified list.
		/// </summary>
		/// <param name="list"></param>
		public LinkedList(IList list) : this()
		{
			AddAll(list);
		}
		#endregion

		#region IList Members

		/// <summary>
		/// Is list read only?
		/// </summary>
		public bool IsReadOnly
		{
			get
			{
				return false;
			}
		}

		/// <summary>
		/// Indexerer.
		/// </summary>
		public object this[int index]
		{
			get
			{
				return GetNode(index).Value;
			}
			set
			{
				GetNode(index).Value = value;
			}
		}

		/// <summary>
		/// Removes the object at the specified index.
		/// </summary>
		/// <param name="index">the index</param>
		/// <exception cref="System.ArgumentOutOfRangeException">if the specified index is greater than
		/// the number of objects within the list</exception>
		public void RemoveAt(int index)
		{
			CheckUpdateState();
			RemoveNode(GetNode(index));
		}

		/// <summary>
		/// Inserts an object at the specified index.
		/// </summary>
		/// <param name="index">the index</param>
		/// <param name="value">the object to be inserted</param>
		/// <exception cref="System.ArgumentOutOfRangeException">if the specified index is greater than
		/// the number of objects within the list</exception>
		public void Insert(int index, object value)
		{
			CheckUpdateState();

			Node node = null;
			if (index == _nodeIndex)
			{
				node = new Node(value, _rootNode.PreviousNode, _rootNode);
			}
			else
			{
				Node insert = GetNode(index);
				node = new Node(value, insert.PreviousNode, insert);
			}
			node.PreviousNode.NextNode = node;
			node.NextNode.PreviousNode = node;
			_nodeIndex++;
			_modId++;
		}

		/// <summary>
		/// Removes the first instance of the specified object found.
		/// </summary>
		/// <param name="value">the object to remove</param>
		public void Remove(object value)
		{
			CheckUpdateState();
			NodeHolder nh = GetNode(value);
			RemoveNode(nh.Node);
		}

		/// <summary>
		/// Tests whether at least one instance of the specified object is
		/// contained within the list.
		/// </summary>
		/// <param name="value">the object to search for</param>
		/// <returns>true if an instance was found, otherwise false</returns>
		public bool Contains(object value)
		{
			return (GetNode(value) != null ? true : false);
		}

		/// <summary>
		/// Removes all objects from the list.
		/// </summary>
		public void Clear()
		{
			_rootNode = new Node(null, null, null);
			_nodeIndex = 0;
			_modId++;
		}

		/// <summary>
		/// Returns the index of the first instance of the specified object found.
		/// </summary>
		/// <param name="value">the object to search for</param>
		/// <returns>the index of the first instance found, or -1</returns>
		/// <exception cref="System.ArgumentOutOfRangeException">if the specified index is greater than
		/// the number of objects within the list</exception>
		public int IndexOf(object value)
		{
			NodeHolder nh = GetNode(value);
			if (nh == null)
			{
				return -1;
			}
			return nh.Index;
		}

		/// <summary>
		/// Adds the specified object to the end of the list.
		/// </summary>
		/// <param name="value">the object to add</param>
		/// <returns>the index the object was added at</returns>
		/// <exception cref="System.ArgumentOutOfRangeException">if the specified index is greater than
		/// the number of objects within the list</exception>
		public int Add(object value)
		{
			Insert(_nodeIndex, value);
			return _nodeIndex - 1;
		}

		/// <summary>
		/// Adds all objects to the end of the list.
		/// </summary>
		/// <param name="list">the list of objects to add</param>
		/// <exception cref="System.ArgumentOutOfRangeException">if the specified index is greater than
		/// the number of objects within the list</exception>
		public void AddAll(IList list)
		{
			foreach(object obj in list)
			{
				Add(obj);
			}
		}

		/// <summary>
		/// Is the list a fixed size?
		/// </summary>
		public bool IsFixedSize
		{
			get
			{
				return false;
			}
		}

		#endregion

		#region Private Methods
		/// <summary>
		/// Checks whether the list can be modified.
		/// </summary>
		/// <exception cref="System.NotSupportedException">if the list
		/// cannot be modified</exception>
		private void CheckUpdateState()
		{
			if (IsReadOnly || IsFixedSize)
			{
				throw new NotSupportedException("LinkedList cannot be modified.");
			}
		}

		/// <summary>
		/// Validates the specified index.
		/// </summary>
		/// <param name="index">the index</param>
		/// <exception cref="System.ArgumentOutOfRangeException">if the index
		/// is invalid</exception>
		private void ValidateIndex(int index)
		{
			if (index < 0 || index >= _nodeIndex)
			{
				throw new ArgumentOutOfRangeException();
			}
		}

		/// <summary>
		/// Returns the node at the specified index.
		/// </summary>
		/// <param name="index">the index</param>
		/// <returns>the node</returns>
		private Node GetNode(int index)
		{
			ValidateIndex(index);

			Node node = _rootNode;
			for (int i = 0 ; i <= index ; i++)
			{
				node = node.NextNode;
			}
			return node;
		}

		/// <summary>
		/// Returns the node (and index) and the first node that contains
		/// the specified value.
		/// </summary>
		/// <param name="value">the value to search for</param>
		/// <returns>the node, or null</returns>
		private NodeHolder GetNode(object value)
		{
			Node node = _rootNode.NextNode;
			for (int i = 0 ; i <= _nodeIndex ; i++)
			{
				if (node.Value.Equals(value))
				{
					return new NodeHolder(node, i);
				}
				else
				{
					node = node.NextNode;
				}
			}
			return null;
		}

		/// <summary>
		/// Removes the specified node.
		/// </summary>
		/// <param name="node">the node</param>
		private void RemoveNode(Node node)
		{
			Node previousNode = node.PreviousNode;
			previousNode.NextNode = node.NextNode;
			node.PreviousNode = null;
			node.NextNode = null;
			_nodeIndex--;
			_modId++;
		}
		#endregion

		#region ICollection Members
		/// <summary>
		/// Is the list synchronized?
		/// </summary>
		public bool IsSynchronized
		{
			get
			{
				return false;
			}
		}

		/// <summary>
		/// The number of objects within the list.
		/// </summary>
		public int Count
		{
			get
			{
				return _nodeIndex;
			}
		}

		/// <summary>
		/// Copies this list to the specified array starting from the specified index.
		/// </summary>
		/// <param name="array">The array to be copied to.</param>
		/// <param name="index">The start index.</param>
		public void CopyTo (Array array, int index)
		{
			if (array == null)
			{
				throw new ArgumentNullException("array", "array cannot be null");
			}

			if (array.Length < (_nodeIndex - index))
			{
				throw new ArgumentException("Array is of insufficient size");
			}
			
			Node node = GetNode(index);
			for (int i = index, pos = 0 ; i < _nodeIndex ; i++, pos++)
			{
				array.SetValue(node.Value, pos);
				node = node.NextNode;
			}
		}

        /// <summary>
        /// Gets an object that can be used to synchronize access to the
        /// <see cref="Spring.Collections.LinkedList"/>.
        /// </summary>
		public object SyncRoot
		{
			get
			{
				return this;
			}
		}

		#endregion

		#region IEnumerable Members

		/// <summary>
		/// Returns an enumerator for this list. Note enumerators are fail fast.
		/// </summary>
		/// <returns>the enumerator</returns>
		public IEnumerator GetEnumerator()
		{
			return new LinkedListEnumerator(this);
		}

		#endregion

		#region Inner Classes
		private class Node
		{
			private object _value;
			private Node _next;
			private Node _previous;

			public object Value
			{
				get
				{
					return _value;
				}
				set
				{
					_value = value;
				}
			}

			public Node NextNode
			{
				get
				{
					return _next;
				}
				set
				{
					this._next = value;
				}
			}

			public Node PreviousNode
			{
				get
				{
					return _previous;
				}
				set
				{
					this._previous = value;
				}
			}

			public Node(object val, Node previous, Node next)
			{
				this._value = val;
				this._next = next;
				this._previous = previous;
			}
		}

		private class NodeHolder
		{
			private int _index;
			private Node _node;

			public int Index
			{
				get
				{
					return _index;
				}
			}

			public Node Node
			{
				get
				{
					return _node;
				}
			}

			public NodeHolder(Node node, int index)
			{
				this._node = node;
				this._index = index;
			}
		}

		private class LinkedListEnumerator : IEnumerator
		{
			private LinkedList _ll;
			private Node _current;
			private int _modId;

			public object Current
			{
				get
				{
					return _current.Value;
				}
			}

			public LinkedListEnumerator(LinkedList ll)
			{
				this._ll = ll;
				this._modId = ll._modId;
				this._current = _ll._rootNode;
			}

			public bool MoveNext()
			{
				if (this._modId != this._ll._modId)
				{
					throw new InvalidOperationException("LinkedList has been modified.");
				}

				_current = _current.NextNode;
				return (_current == _ll._rootNode ? false : true);
			}

			public void Reset()
			{
				_current = _ll._rootNode;
			}
		}
		#endregion
	}
}
